

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution
{
public:
    string longestCommonPrefix1(vector<string>& strs)
    {
        int n = strs.size();

        if (1 == n)
            return strs[0];

        string res = strs[0];
        for (int i = 1; i < n; ++i)
        {
            res = findCmn(res, strs[i]);
        }

        return res;
    }

    string longestCommonPrefix2(vector<string>& strs)
    {
        int n = strs.size();

        if (1 == n)
            return strs[0];

        string res = strs[0];
        for (int i = 0; i < strs[0].size(); ++i)
        {
            int ch = strs[0][i];

            for (int j = 0; j < n; ++j)
            {
                if (i == strs[j].size() || strs[j][i] != ch)
                    return strs[0].substr(0, i);
            }
        }

        return res;
    }

    string longestPalindrome1(string s)
    {
        int n = s.size();

        if (1 == n)
            return s;

        int beg = 0, len = 0;

        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j < n; ++j)
            {
                if (isAns(s, i, j))
                {
                    if (j - i + 1 > len)
                    {
                        beg = i;
                        len = j - i + 1;
                    }
                }
            }
        }

        return s.substr(beg, len);
    }

    string longestPalindrome2(string s)
    {
        int n = s.size();

        if (1 == n)
            return s;

        string res;
        int beg = 0, len = 0;

        for (int i = 0; i < n; ++i)
        {
            int lf = i - 1, rg = i + 1;

            while (lf >= 0 && rg < n && s[lf] == s[rg])
            {
                --lf;
                ++rg;
            }
            if (rg - lf - 1 > len)
            {
                beg = lf + 1;
                len = rg - lf - 1;
            }

            lf = i, rg = i + 1;
            while (lf >= 0 && rg < n && s[lf] == s[rg])
            {
                --lf;
                ++rg;
            }
            if (rg - lf - 1 > len)
            {
                beg = lf + 1;
                len = rg - lf - 1;
            }
        }

        return s.substr(beg, len);
    }

    string addBinary1(string a, string b)
    {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int sum = 0;
        string res;
        int an = a.size(), bn = b.size();

        for (int i = 0, j = 0; i < an || j < bn || sum; ++i, ++j)
        {
            if (i < an)
                sum += a[i] - '0';
            if (j < bn)
                sum += b[j] - '0';
            res += to_string(sum % 2);
            sum /= 2;
        }
        reverse(res.begin(), res.end());

        return res;
    }

    string addBinary2(string a, string b)
    {
        string res;
        int sum = 0;
        int an = a.size(), bn = b.size();

        for (int i = an - 1, j = bn - 1; i >= 0 || j >= 0 || sum; --i, --j)
        {
            if (i >= 0)
                sum += a[i] - '0';
            if (j >= 0)
                sum += b[j] - '0';
            res += to_string(sum % 2);
            sum /= 2;
        }
        reverse(res.begin(), res.end());

        return res;
    }

    string multiply1(string s1, string s2)
    {
        if ("0" == s1 || "0" == s2)
            return "0";
        if ("1" == s1)
            return s2;
        if ("1" == s2)
            return s1;

        string res;
        int n1 = s1.size(), n2 = s2.size();
        vector<string> vs(n2);

        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());

        for (int i = 0; i < n2; ++i)
        {
            vs[i] = _mulone(s1, s2[i] - '0');
        }

        for (int i = 0; i < n2; ++i)
        {
            _sum(res, vs[i], i);
        }

        while ('0' == res.back())
        {
            res.pop_back();
        }
        reverse(res.begin(), res.end());

        return res;
    }

    string multiply2(string num1, string num2)
    {
        if ("0" == num1 || "0" == num2)
            return "0";
        if ("1" == num1)
            return num2;
        if ("1" == num2)
            return num1;


        int n1 = num1.size(), n2 = num2.size();
        vector<int> v(n1 + n2 - 1);

        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < n1; ++i)
        {
            for (int j = 0; j < n2; ++j)
            {
                v[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        string res;
        int carry = 0;

        for (int i = 0; i < n1 + n2 - 1 || carry; ++i)
        {
            if (i < n1 + n2 - 1)
                carry += v[i];
            res += carry % 10 + '0';
            carry /= 10;
        }
        reverse(res.begin(), res.end());

        return res;
    }

private:
    string _mulone(const string& s, int digit)
    {
        if (!digit)
            return "0";
        if (1 == digit)
            return s;

        string res;
        int sum = 0;
        int n = s.size();

        for (int i = 0; i < n || sum; ++i)
        {
            if (i < n)
                sum += (s[i] - '0') * digit;

            res += sum % 10 + '0';
            sum /= 10;
        }

        return res;
    }

    void _sum(string& res, string& s, int cnt)
    {
        if ("0" == s)
            return;

        string tmp;

        while (cnt--)
        {
            tmp += "0";
        }
        s = tmp + s;
        tmp.clear();

        int sum = 0;
        int n1 = res.size(), n2 = s.size();

        for (int i = 0, j = 0; i < n1 || j < n2 || sum; ++i, ++j)
        {
            if (i < n1)
                sum += res[i] - '0';
            if (j < n2)
                sum += s[j] - '0';
            tmp += sum % 10 + '0';
            sum /= 10;
        }

        res = tmp;
    }

    bool isAns(const string& s, int i, int j)
    {
        string tmp = s.substr(i, j - i + 1);
        int n = tmp.size();

        for (int i = 0, j = n - 1; i < j; ++i, --j)
        {
            if (tmp[i] != tmp[j])
                return false;
        }

        return true;
    }

    string findCmn(const string& s1, const string& s2)
    {
        int index = 0;
        int n = min(s1.size(), s2.size());

        while (index < n && s1[index] == s2[index])
        {
            ++index;
        }

        return s1.substr(0, index);
    }
};

void Test1()
{
    Solution().multiply1("123456789", "987654321");
#if 0
    string s1 = "123456789";
    string s2 = "987654321";

    for (int i = 0; i < 9; ++i)
    {
        string tmp = to_string(123456789 * (i + 1));
        reverse(tmp.begin(), tmp.end());

        cout << (long long)123456789 * (i + 1) << "  " << tmp << endl;
    }
    
#endif
}

int main()
{
    Test1();


	return 0;
}